package com.learn.finished;

import java.util.Arrays;

public class num_1991 {
    /**
     * 给你一个下标从 0 开始的整数数组 nums ，请你找到 最左边 的中间位置 middleIndex （也就是所有可能中间位置下标最小的一个）。
     *
     * 中间位置 middleIndex 是满足 nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1] 的数组下标。
     *
     * 如果 middleIndex == 0 ，左边部分的和定义为 0 。类似的，如果 middleIndex == nums.length - 1 ，右边部分的和定义为 0 。
     *
     * 请你返回满足上述条件 最左边 的 middleIndex ，如果不存在这样的中间位置，请你返回 -1 。
     *
     *
     * 输入：nums = [2,3,-1,8,4]
     * 输出：3
     * 解释：
     * 下标 3 之前的数字和为：2 + 3 + -1 = 4
     * 下标 3 之后的数字和为：4 = 4
     *
     *
     * 输入：nums = [1,-1,4]
     * 输出：2
     * 解释：
     * 下标 2 之前的数字和为：1 + -1 = 0
     * 下标 2 之后的数字和为：0
     *
     * 输入：nums = [2,5]
     * 输出：-1
     * 解释：
     * 不存在符合要求的 middleIndex
     *
     * 输入：nums = [1]
     * 输出：0
     * 解释：
     * 下标 0 之前的数字和为：0
     * 下标 0 之后的数字和为：0
     */
    public static void main(String[] args) {
        int[] nums={1,1};
        int middleIndex = findMiddleIndex1(nums);
        System.out.println(middleIndex);

    }

    private static int findMiddleIndex1(int[] nums) {
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        int leftSum = 0;
        for(int i=0;i<nums.length;i++){
            sum -= nums[i];
            if(leftSum == sum){
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }

    /**
     * 超出时间限制？草，有狗，{1,1}
     * @param nums
     * @return
     */
    public static int findMiddleIndex(int[] nums) {
        //首先，返回输出的是下标,有点类似求中位数，左边+右边是相等的，而且nums[mid]不参与其中的运算
        //是否可以用首尾双指针，同时向中间移动，期间相加，判断大小进行下一步
        if (nums.length == 1) {
            return 0;
        }
        int left=0;
        int right=nums.length-1;
        int leftSum=nums[left];
        int rightSum=nums[right];
        //那循环的开始条件是什么？终止条件又是什么？
        while (left < right) {
//            leftSum+=nums[left];
//            rightSum+=nums[right];
            if (leftSum < rightSum) {
                leftSum+=nums[++left];
            } else if (leftSum > rightSum) {
                rightSum += nums[--right];
//                right--;
            }
        }
        if (leftSum != rightSum) {
            return -1;
        }
        return left;
    }
}
